
/*************
author:: libo
license:: MIT
*****************/
#include<Mesh/_Func_.h>
#include<Mesh/libcell_iterator.h>

#define iterator_v lib_cell_iterator_vertices
#define iterator_f lib_cell_iterator_faces
#define iterator_c lib_cell_iterator_cells
#define iterator_edge lib_cell_iterator_edge

#define quote lib_cell_quote
template_v* Mesh_get_vertexp(struct Mesh* m, int i)
{
	return (template_v*)(m->vertices->find(m->vertices, i));
}
template_c* Mesh_get_cellp(struct Mesh* m, int i)
{
	return (template_c*)(m->cells->find(m->cells, i));
}
template_f* Mesh_get_facep(struct Mesh* m, int i)
{
	return (template_f*)(m->faces->find(m->faces, i));
}
template_hf* Mesh_get_halffacep(struct Mesh* m, int i)
{
	return (template_hf*)(m->halffaces->find(m->halffaces, i));
}
template_v Mesh_get_vertex(struct Mesh* own, int id)
{

	template_v* v = Mesh_get_vertexp(own, id);
	if (v != NULL)
	{
		return *v;
	}
	template_v v1;
	Vertex_init_(&v1);
	return v1;

}
template_c Mesh_get_cell(struct Mesh* own, int id)
{

	template_c* c = Mesh_get_cellp(own, id);
	if (c != NULL)
	{
		return *c;
	}
	template_c c1;
	Cell_init_(&c1);
	return c1;

}
template_f Mesh_get_face(struct Mesh* own, int id)
{

	template_f* f = Mesh_get_facep(own, id);
	if (f != NULL)
	{
		return *f;
	}
	template_f f1;
	Face_init_(&f1);
	return f1;
}
template_hf Mesh_get_halfface(struct Mesh* own, int id)
{
	template_hf* hf = Mesh_get_halffacep(own, id);
	if (hf != NULL)
	{
		return *hf;
	}
	template_hf hf1;
	HalfFace_init_(&hf1);
	return hf1;

}
template_f* Mesh_get_facev(struct Mesh* own, template_v** temp_v, int size)
{

	Node* node = temp_v[0]->faces;
	bool b = false;
	while (node != NULL)
	{
		b = true;
		for (int i = 1; i < size; i++)
		{
			if (node_find(temp_v[i]->faces, node->value) == NULL)
			{
				b = false;
				break;
			}
		}
		if (b)
		{
			break;
		}
		node = (Node*)(node->Next);
	}

	if (b)
	{
		return (template_f*)(node->value);
	}

	return NULL;
}
template_c* Mesh_get_cellv(struct Mesh* own, template_v** temp_v, int size)
{
	Node* node = temp_v[0]->cells;
	bool b = false;
	while (node != NULL)
	{
		b = true;
		for (int i = 1; i < size; i++)
		{
			if (node_find(temp_v[i]->cells, node->value) == NULL)
			{
				b = false;
				break;
			}
		}
		if (b)
		{
			break;
		}
		node = (Node*)(node->Next);
	}
	if (b)
	{
		return (template_c*)(node->value);

	}
	return NULL;

}
template_c* Mesh_get_cellf(struct Mesh* own, template_f** temp_f, int size)
{
	bool b = false;
	int i = 0;
	for (i = 0; i < 2; i++)
	{
		if (temp_f[0]->halffaces[i]->cell == NULL)
		{
			//b=false;
			continue;

		}
		b = true;
		for (int j = 1; j < size; j++)
		{
			if (temp_f[j]->halffaces[0]->cell == temp_f[0]->halffaces[i]->cell || temp_f[j]->halffaces[1]->cell == temp_f[0]->halffaces[i]->cell)
			{
				continue;
			}
			else
			{
				b = false;
				break;
			}
		}
		if (b)
		{
			break;
		}


	}
	if (b)
	{
		return (template_c*)temp_f[0]->halffaces[i]->cell;
	}
	return NULL;


}

int Mesh_num_c(struct Mesh* own)
{
	return own->cells->size;
	//return own->cells.size();
}
int Mesh_num_f(struct Mesh* own)
{
	return own->faces->size;
	//return own->faces.size();
}
int Mesh_num_v(struct Mesh* own)
{
	return own->vertices->size;
	//return own->vertices.size();
}
int Mesh_num_hf(struct Mesh* own)
{

	return own->halffaces->size;
	//return own->halffaces.size();
}
template_v* Mesh_create_vertex(struct Mesh* own)
{
	template_v* v = (template_v*)malloc(sizeof(template_v));

	Vertex_init_(v);
	v->id = own->vertex_id++;
	//own->vertices[v->id]=v;
	own->vertices->insert(own->vertices, v->id, v);
	return v;
}
template_v* Mesh_create_vertexv(struct Mesh* own, double* p, int size)
{

	template_v* v = Mesh_create_vertex(own);
	v->point_size = size;
	v->point = (double*)malloc(sizeof(double) * size);
	for (int i = 0; i < size; i++)
	{
		v->point[i] = p[i];

	}
	return v;
}
template_f* Mesh_create_face(struct Mesh* own)
{
	template_f* f = (template_f*)malloc(sizeof(template_f));
	Face_init_(f);
	f->halffaces[0]->cell = NULL; f->halffaces[1]->cell = NULL;
	f->id = own->face_id++;

	//own->faces[f->id]=f;
	own->faces->insert(own->faces, f->id, f);
	return f;

}
template_c* Mesh_create_cell(struct Mesh* own)
{
	template_c* c = (template_c*)malloc(sizeof(template_c));

	Cell_init_(c);
	c->id = own->cell_id++;

	//own->cells[c->id]=c;
	own->cells->insert(own->cells, c->id, c);

	return c;
}
//如果返回NULL,意味创建失败
template_hf* Mesh_create_halfface(struct Mesh* own, template_f* f, template_v** temp_v, int size)
{
	if (f == NULL)
	{
		return 0;
	}
	if (f->halffaces[0]->cell != NULL && f->halffaces[1]->cell != NULL)
	{
		return NULL;
	}


	template_hf* hf = NULL;
	if (f->halffaces[0]->vertices == NULL)
	{
		hf = f->halffaces[0];
	}
	else if (f->halffaces[1]->vertices == NULL)
	{

		hf = f->halffaces[1];
	}
	else
	{
		if (f->halffaces[0]->cell == NULL)
		{
			hf = f->halffaces[0];
		}
		else if (f->halffaces[1]->cell == NULL)
		{
			hf = f->halffaces[1];
		}
		else
		{

			printf("流形的网格拓扑错误\n");
			for (int i = 0; i < size; i++)
			{
				printf("%d ", temp_v[i]->id);
			}
			printf("\n");
			return NULL;
		}
	}
	hf->id = own->halfface_id++;

	//own->halffaces[hf->id]=hf;
	own->halffaces->insert(own->halffaces, hf->id, hf);

	if (hf->vertices == NULL)
	{
		hf->vertices = (template_v**)malloc(sizeof(template_v*) * size);
	}
	for (int i = 0; i < size; i++)
	{
		hf->vertices[i] = temp_v[i];
	}
	hf->vertices_size = size;


	return hf;
}
//以下程序表明点到face的遍历没有不能保证顺(逆)时针(当cell是曲面)
template_f* Mesh_create_facev(struct Mesh* own, template_v** temp_v, int size)
{
	template_f* f = Mesh_get_facev(own, temp_v, size);
	if (f == NULL)
	{
		f = Mesh_create_face(own);
	}
	else
	{
		return f;
	}
	f->vertices_size = size;
	f->vertices = (template_v**)malloc(sizeof(template_v*) * size);
	for (int i = 0; i < size; i++)
	{

		f->vertices[i] = temp_v[i];
		temp_v[i]->faces = node_overlying(temp_v[i]->faces, (void*)f);

	}
	return f;
}
//要判断是否已经创建相应的cell
template_c* Mesh_create_cellf(struct Mesh* own, template_hf** temp_hf, int size)
{
	//#ifdef __DEBUG__
	for (int i = 0; i < size; i++)
	{
		if (temp_hf[i] == NULL)
		{
			printf("create cellf temp_hf i is NULL\n");
			return NULL;
		}
	}
	//#endif

	if (temp_hf[0]->cell != NULL)
	{
		//exist cell
		return temp_hf[0]->cell;
	}
	template_c* c = Mesh_create_cell(own);

	Node* node = NULL, * node_v = NULL;
	for (int i = 0; i < size; i++)
	{
		temp_hf[i]->cell = c;
		node = node_overlying(node, (void*)temp_hf[i]);
		for (int j = 0; j < temp_hf[i]->vertices_size; j++)
		{
			if (node_find(node_v, temp_hf[i]->vertices[j]) == NULL)
			{
				node_v = node_overlying(node_v, temp_hf[i]->vertices[j]);

			}
		}
	}

	c->halffaces = node;

	Node* temp_nodev = node_v;
	node_v = node_reverse(node_v);
	int le = node_size(node_v);
	c->vertices = (template_v**)malloc(sizeof(template_v*) * le);
	c->vertices_size = le;
	int i = 0;
	while (node_v != NULL)
	{
		c->vertices[i] = (template_v*)(node_v->value);


		((template_v*)(node_v->value))->cells = node_overlying(((template_v*)(node_v->value))->cells, (void*)c);
		node_v = (Node*)(node_v->Prev);
		i++;
	}
	free_node(temp_nodev);
	return c;
}
//应该写 Mesh_get_cellv，并用在下面判断(但速度会变慢)
//以下程序也不能保证点到cell的遍历是顺(逆)时针(当cell表示面时)
//创建单形使用的函数
//如果返回NULL意味创建失败
template_c* Mesh_create_cellv(struct Mesh* own, template_v** temp_v, int size)
{
	template_c* ccc = Mesh_get_cellv(own, temp_v, size);

	if (ccc != NULL)
	{
		return ccc;
	}

	template_hf** hfs = (template_hf**)malloc(sizeof(template_hf*) * size);
	template_v** temp_v1 = (template_v**)malloc(sizeof(template_v*) * (size - 1));
	for (int i = 0; i < size; i++)
	{
		int temp_i = 0;
		for (int j = 0; j < size; j++)
		{
			if (j != i)
			{

				temp_v1[temp_i] = temp_v[j];
				temp_i++;
			}
		}
		if ((size - i - 1) % 2 == 0)
		{
		}
		else if (size > 2)
		{
			template_v* vv = temp_v1[0];
			temp_v1[0] = temp_v1[1];
			temp_v1[1] = vv;
		}
		template_f* f = Mesh_create_facev(own, temp_v1, size - 1);
		hfs[i] = Mesh_create_halfface(own, f, temp_v1, size - 1);

		if (hfs[i] == NULL)
		{
			printf("create cellv is NULL\n");
			for (int j = 0; j < size - 1; j++)
			{
				printf("v : %d \n", temp_v1[j]->id);
			}
			printf("f :%d\n", f->id);
			if (own->manifold_require == 1)
			{
				Int_RB_Tree* temp_tree = (Int_RB_Tree*)malloc(sizeof(Int_RB_Tree));
				int_rb_tree_init(temp_tree);
				for (int j = 0; j < i; j++)
				{
					own->halffaces->erase(own->halffaces, hfs[j]->id);
					SAFE_FREE(hfs[j]->vertices);
					hfs[j]->vertices_size = 0;
					if (hfs[j]->face->halffaces[0]->cell == NULL && hfs[j]->face->halffaces[1]->cell == NULL)
					{
						temp_tree->insert(temp_tree, hfs[j]->face->id, hfs[j]->face);
					}
				}
				if (f->halffaces[0]->cell == NULL && f->halffaces[1]->cell == NULL)
				{
					temp_tree->insert(temp_tree, f->id, f);
				}
				for (auto it = temp_tree->begin(temp_tree); it.it != NULL; it++)
				{
					template_f* ff1 = (template_f*)(it.second);
					own->faces->erase(own->faces, ff1->id);
					for (int k = 0; k < ff1->vertices_size; k++)
					{
						Vertex_remove_f(ff1->vertices[k], ff1);
					}
					free_Face(ff1);
				}
				int_rb_tree_free(temp_tree);
			}
			free(temp_v1); free(hfs);
			return NULL;
		}
	}

	template_c* c = Mesh_create_cell(own);
	c->vertices = (template_v**)malloc(sizeof(template_v*) * size);
	c->vertices_size = size;

	for (int i = 0; i < size; i++)
	{
		c->vertices[i] = temp_v[i];

		temp_v[i]->cells = node_overlying(temp_v[i]->cells, (void*)c);
		//#ifdef SIMPLEX_REQUIRE   

		hfs[i]->cell = c;
		c->halffaces = node_overlying(c->halffaces, (void*)(hfs[i]));
		//#endif
	}
	free(hfs);
	free(temp_v1);

	return c;
}
int Mesh_delete_vertex(struct Mesh* own, template_v v_, int burning)
{
	template_v* v = NULL;

	Int_RB_Tree_Node* it = int_rb_tree_find(own->vertices, v_.id);
	if (it == NULL)
	{
		return 0;
	}
	else
	{
		v = (template_v*)(it->data);
		int_rb_tree_delete_node(own->vertices, it);
	}
	template_c* c;
	Node* node = node_copy(v->cells), * node1 = NULL, * node2 = NULL;
	node1 = node;
	while (node1 != NULL)
	{
		node2 = (Node*)(node1->Next);
		c = (template_c*)(node1->value);
		Mesh_delete_cell(own, *c, true);
		node1 = node2;

	}
	free_node(node);


	//#ifndef MANIFOLD_REQUIRE
	if (own->manifold_require == 0)
	{
		node = node_copy(v->faces);
		template_f* f;
		node1 = node;
		while (node1 != NULL)
		{
			node2 = (Node*)(node1->Next);
			f = (template_f*)(node1->value);
			Mesh_delete_face(own, *f, true);
			node1 = node2;
		}
		free_node(node);
	}
	//#endif

	if (burning)
	{
		free_Vertex(v);
	}

	return 1;
}
int Mesh_delete_halfface(struct Mesh* own, template_hf f_, int burning)
{
	template_hf* hf = NULL;


	Int_RB_Tree_Node* it = int_rb_tree_find(own->halffaces, f_.id);
	if (it != NULL)
	{
		hf = (template_hf*)(it->data);
	}
	else
	{
		return false;
	}

	if (hf->cell != NULL)
	{
		Mesh_delete_cell(own, *((template_c*)(hf->cell)), burning);
		hf->cell = NULL;
	}
	//#ifndef MANIFOLD_REQUIRE
	if (own->manifold_require == 0)
	{
		if (hf->vertices != NULL)
		{
			free(hf->vertices);
			hf->vertices = NULL;
		}
		hf->vertices_size = 0;
		//own->halffaces.erase(it);
		int_rb_tree_delete_node(own->halffaces, it);
	}

	//#endif

	return true;
}
int Mesh_delete_face(struct Mesh* own, template_f f_, int burning)
{
	template_f* f = NULL;

	Int_RB_Tree_Node* it = int_rb_tree_find(own->faces, f_.id);
	if (it != NULL)
	{
		f = (template_f*)(it->data);
	}
	else
	{
		return false;
	}
	for (int i = 0; i < 2; i++)
	{
		if (f->halffaces[i]->cell != NULL)
		{
			Mesh_delete_cell(own, *(f->halffaces[i]->cell), burning);
		}
	}

	//#ifndef MANIFOLD_REQUIRE
	if (own->manifold_require == 0)
	{
		int_rb_tree_delete_node(own->faces, it);
		for (int i = 0; i < f->vertices_size; i++)
		{
			Vertex_remove_f((template_v*)f->vertices[i], f);
		}
		if (burning)
		{
			free_Face(f);
		}
	}

	//#endif
	return true;
}
int Mesh_delete_cell(struct Mesh* own, template_c c_, int burning)
{
	template_c* c;
	Int_RB_Tree_Node* it = int_rb_tree_find(own->cells, c_.id);
	if (it != NULL)
	{
		c = (template_c*)(it->data);
		int_rb_tree_delete_node(own->cells, it);
	}
	else
	{
		return false;
	}

	//handle with face
	template_f* f;
	Node* node = c->halffaces, * node1 = NULL;
	while (node != NULL)
	{
		node1 = (Node*)(node->Next);
		//  f=(template_f*)(((template_hf*)node->value)->face);
		  //face要甩掉cell
		  //Face_remove_c(f,c);
		Halfface_remove_c((template_hf*)(node->value), c);

		// auto hfit=own->halffaces.find(((template_hf*)(node->value))->id);
		// if(hfit!=own->halffaces.end())
		// {
		//     own->halffaces.erase(hfit);
		// }
		own->halffaces->erase(own->halffaces, ((template_hf*)(node->value))->id);
		node = node1;
	}
	template_v* v;
	for (int i = 0; i < c->vertices_size; i++)
	{
		v = (template_v*)c->vertices[i];
		Vertex_remove_c(v, c);
	}
	//#ifdef MANIFOLD_REQUIRE
	if (own->manifold_require == 1)
	{
		Node* node_f = c->halffaces;
		while (node_f != NULL)
		{
			f = (template_f*)((template_hf*)(node_f->value))->face;
			if (f->halffaces[0]->cell == NULL && f->halffaces[1]->cell == NULL)
			{
				for (int i = 0; i < f->vertices_size; i++)
				{
					Vertex_remove_f((template_v*)f->vertices[i], f);

				}

				own->halffaces->erase(own->halffaces, f->halffaces[0]->id);
				own->halffaces->erase(own->halffaces, f->halffaces[1]->id);
				own->faces->erase(own->faces, f->id);


				if (burning)
				{
					free_Face(f);
				}
			}
			node_f = (Node*)(node_f->Next);

		}
		//
		//如果要严格删除孤立点，则取消注释一下代码
			//*************
	/*    for(int i=0;i<c->vertices_size;i++)
		{
			v=(template_v*)(c->vertices[i]);
			if(v->cells==NULL)
			{
				auto vit=own->vertices.find(v->id);
				if(vit!=own->vertices.end())
				{
					own->vertices.erase(vit);
				}
				free_Vertex(v);
			}

		}
	  */
	}

	//#endif

	if (burning)
	{
		free_Cell(c);

	}
	return true;
}
int Mesh_face_is_boundary(struct Mesh* own, template_f* f)
{

	return Mesh_nface_is_boundary(own, *f);
}
int Mesh_nface_is_boundary(struct Mesh* own, template_f f)
{
	if (f.halffaces[0]->cell == NULL || f.halffaces[1]->cell == NULL)
	{
		return true;
	}
	return false;
}
int Mesh_cell_is_boundary(struct Mesh* own, template_c c)
{
	for (Node* nit = c.halffaces; nit != NULL; nit = (Node*)(nit->Next))
	{
		template_hf* hf = (template_hf*)(nit->value);
		if (Mesh_nface_is_boundary(own, *(hf->face)))
		{
			return 1;
		}
	}
	return 0;
}

//孤立点也是边界点
int Mesh_vertex_is_boundary(struct Mesh* own, template_v v)
{
	Node* node = v.faces;
	if (node == NULL)
	{
		return true;
	}
	while (node != NULL)
	{
		if (Mesh_nface_is_boundary(own, *((template_f*)(node->value))))
		{
			return true;
		}
		node = (Node*)(node->Next);
	}
	return false;
}
int Mesh_face_is_in_cell(struct Mesh* own, template_f* f, template_c* c)
{
	for (Node* nit = c->halffaces; nit != NULL; nit = (Node*)(nit->Next))
	{
		template_hf* hf = (template_hf*)(nit->value);
		if (hf->face == f)
		{
			return true;
		}
	}
	return false;
}
int Mesh_vertex_is_in_cell(struct Mesh* own, template_v* v, template_c* c)
{
	for (int i = 0; i < c->vertices_size; i++)
	{
		if (c->vertices[i] == v)
		{
			return true;
		}
	}
	return false;
}
int Mesh_vertex_is_in_face(struct Mesh* own, template_v* v, template_f* f)
{
	for (int i = 0; i < f->vertices_size; i++)
	{
		if (f->vertices[i] == v)
		{
			return true;
		}
	}
	return false;
}
//
//给它一个初始面，他会返回boundary的node链.这种寻找边界的方式.
//返回半边
//用红黑树RB_Tree做标记，代替prop
//
Node* Mesh_node_of_boundary_face(struct Mesh* own, template_f* f_)
{

	Int_RB_Tree* tree = (Int_RB_Tree*)malloc(sizeof(Int_RB_Tree));
	int_rb_tree_init(tree);

	if (f_ == NULL)
	{
		int_rb_tree_free(tree);
		return NULL;
	}
	Node* node = NULL, * node3 = NULL;
	template_f* f = NULL;

	template_hf* hf = NULL;
	f = (template_f*)(own->faces->find(own->faces, f_->id));
	if (f == NULL)
	{
		return NULL;
	}

	if (!Mesh_nface_is_boundary(own, *f_))
	{
		return NULL;
	}
	else
	{
		node = node_overlying(node, (void*)f);

		if (f->halffaces[1]->cell == NULL)
		{
			hf = f->halffaces[1];
			node3 = node_overlying(node3, (void*)hf);
		}
		if (f->halffaces[0]->cell == NULL)
		{
			hf = f->halffaces[0];
			node3 = node_overlying(node3, (void*)hf);
		}

	}

	// 深度优先的遍历
 //   printf("shendu\n");

	template_v* v = NULL;
	Node* node2 = NULL;
	while (node != NULL)
	{
	push:
		f = (template_f*)(node->value);
		//        printf("f : %d\n",f->id);
		if (f->halffaces[0]->cell != NULL)
		{
			hf = f->halffaces[0];
		}
		else
		{
			hf = f->halffaces[1];
		}

		tree->insert(tree, f->id, f);

		for (int i = 0; i < hf->vertices_size; i++)
		{
			v = (template_v*)(hf->vertices[i]);
			node2 = v->faces;
			while (node2 != NULL)
			{
				if (Mesh_nface_is_boundary(own, *((template_f*)(node2->value))))
				{
					void* var = tree->find(tree, ((template_f*)(node2->value))->id);
					//if(rbt1==NULL)
					if (var == NULL)
					{
						node = node_overlying(node, node2->value);
						void* temp_value = NULL;
						if (((template_f*)node2->value)->halffaces[0]->cell == NULL)
						{
							temp_value = (void*)(((template_f*)node2->value)->halffaces[0]);
							node3 = node_overlying(node3, temp_value);
						}
						else if (((template_f*)node2->value)->halffaces[1]->cell == NULL)
						{
							temp_value = (void*)(((template_f*)node2->value)->halffaces[1]);
							node3 = node_overlying(node3, temp_value);
						}
						goto push;
					}
				}
				node2 = (Node*)(node2->Next);
			}
		}
		Node* node1 = node;
		node = (Node*)node->Next;
		free(node1);
		node1 = NULL;
	}
	int_rb_tree_free(tree);
	return node3;
}
static Node* Mesh_one_dim_boundary(struct Mesh* own)
{
	Node* node = NULL;
	// for(auto it=own->faces.begin();it!=own->faces.end();it++)
	// {
	//     if(it->second->halffaces[0]->cell==NULL)
	//     {
	//         node=node_overlying(node,it->second->halffaces[0]);
	//     }
	//     else if(it->second->halffaces[1]->cell==NULL)
	//     {
	//         node=node_overlying(node,it->second->halffaces[1]);
	//     }
	// }
	for (auto it = Mesh_f_beginn(own); it != Mesh_f_endn(own); it++)
	{
		if (((template_f*)(quote(it)))->halffaces[0]->cell == NULL)
		{
			node = node_overlying(node, ((template_f*)(quote(it)))->halffaces[0]);
		}
		else if (((template_f*)(quote(it)))->halffaces[1]->cell == NULL)
		{
			node = node_overlying(node, ((template_f*)(quote(it)))->halffaces[1]);
		}
	}


	return node;
}
//
void Mesh_external_cell_init_(struct Mesh* own)
{

	free_node(own->external_cell.halffaces);
	own->external_cell.halffaces = NULL;
	//#ifdef MANIFOLD_REQUIRE
	if (own->dimension == 1 && own->manifold_require == 1)
	{
		own->external_cell.halffaces = Mesh_one_dim_boundary(own);
		//            printf("external_cell size:%d\n",node_size(own->external_cell.halffaces));

		return;
	}
	//#endif
	for (auto it = Mesh_f_beginn(own); it != Mesh_f_endn(own); it++)
	{
		if (Mesh_nface_is_boundary(own, *((template_f*)(quote(it)))))
		{
			own->external_cell.halffaces = Mesh_node_of_boundary_face(own, ((template_f*)(quote(it))));

			break;
		}
	}
	// for(auto it=own->faces.begin();it!=own->faces.end();it++)
	// {   
	//     if(Mesh_nface_is_boundary(own,*(it->second)))
	//     {
	//         own->external_cell.halffaces=Mesh_node_of_boundary_face(own,it->second);
	//         break;
	//     }
	// }
	template_hf* hf1, * hf2;
	Node* node = own->external_cell.halffaces;

	//  printf("external_cell size:%d\n",node_size(node));
	if (node == NULL)
	{
		return;
	}
	//reset_f_prop(own);
	own->external_cell.vertices_size = node_size(node);
	own->external_cell.vertices = (template_v**)malloc(sizeof(template_v*) * own->external_cell.vertices_size);
	int i = 0;
	while (node != NULL)
	{
		hf1 = (template_hf*)(node->value);
		if (hf1->vertices != NULL)
		{
			free(hf1->vertices);
			hf1->vertices = NULL;
		}

		hf2 = Mesh_s_opposite_halfface(hf1);
		hf1->vertices = (template_v**)malloc(sizeof(template_v*) * hf2->vertices_size);

		hf1->vertices_size = hf2->vertices_size;
		for (int i = 0; i < hf2->vertices_size; i++)
		{
			hf1->vertices[i] = hf2->vertices[i];
			//              printf("external cell h_f id:%d ",((template_v*)(hf1->vertices[i]))->id);
		}
		if (hf1->vertices_size >= 2)
		{
			template_v* temp = hf1->vertices[0];
			hf1->vertices[0] = hf1->vertices[1];
			hf1->vertices[1] = temp;
		}
		own->external_cell.vertices[i] = hf1->vertices[0];
		i++;
		node = (Node*)(node->Next);
	}
}
template_hf Mesh_opposite_halfface(template_hf hf)
{
	template_f* f = (template_f*)hf.face;
	if (f->halffaces[0]->cell == hf.cell)
	{
		return *(f->halffaces[1]);
	}
	else
	{
		return *(f->halffaces[0]);

	}
}
template_hf* Mesh_s_opposite_halfface(template_hf* hf)
{
	template_f* f = (template_f*)(hf->face);
	if (f->halffaces[0] == hf)
	{
		return f->halffaces[1];
	}
	else if (f->halffaces[1] == hf)
	{
		return f->halffaces[0];
	}
	return NULL;
}
//需要修改的函数
Node* Mesh_non_manifold_vertices(struct Mesh* own)
{
	Node* re = NULL;
	for (auto iter = Mesh_v_beginn(own); iter != Mesh_v_endn(own); iter++)
	{
		if (((template_v*)(quote(iter)))->cells == NULL)
		{
			re = node_overlying(re, quote(iter));
		}
	}
	// for(auto iter=own->vertices.begin();iter!=own->vertices.end();iter++)
	// {
	//     if(iter->second->cells==NULL)
	//     {
	//         re=node_overlying(re,iter->second);

	//     } 
	// }
	return re;
}
int Mesh_two_cell_is_connected(struct Mesh* own, template_c* c1, template_c* c2)
{
	bool re = false;
	if (c1 == NULL || c2 == NULL)
	{
		return re;
	}

	for (auto hfit = Mesh_chf_begin(own, *c1); hfit != Mesh_chf_end(own, *c1); hfit++)
	{
		if (Mesh_s_opposite_halfface(quote(hfit))->cell == c2)
		{
			return true;
		}
	}
	return re;

}
int Mesh_is_manifold_vertices(struct Mesh* own, template_v* v)
{
	if (v->cells == NULL)
	{
		return false;
	}
	Node* ncs = node_copy(v->cells);
	Node* n1 = ncs, * n2 = (Node*)(n1->Next);

	n1->Next = NULL;
	if (n2 != NULL)
	{
		n2->Prev = NULL;
	}
	int flag = 0;
	do {
		flag = 0;
		for (Node* nit = n2; nit != NULL; nit = (Node*)(nit->Next))
		{
			for (Node* nnit = n1; nnit != NULL; nnit = (Node*)(nnit->Next))
			{

				if (Mesh_two_cell_is_connected(own, (template_c*)(nit->value), (template_c*)(nnit->value)))
				{
					flag = 1;
					n1 = node_overlying(n1, nit->value);
					n2 = node_delete_value(n2, nit->value);
					break;
				}


			}
			if (flag == 1)
			{
				break;
			}

		}

	} while (flag == 1);
	if (n2 == NULL)
	{
		free_node(n1);
		return true;
	}
	else
	{

		free_node(n1);
		return false;
	}

	//Node* re[2]={NULL,NULL};
   // Node* n1=v->cells,*n2=(Node*)(n1->Next);


	return true;
}
void Mesh_reset_c_prop(struct Mesh* mesh)
{
	// for(auto cit=mesh->cells.begin();cit!=mesh->cells.end();cit++)
	// {
	// cit->second->prop=NULL;
	// }
	for (auto cit = Mesh_c_beginn(mesh); cit != Mesh_c_endn(mesh); cit++)
	{
		((template_c*)(quote(cit)))->prop = NULL;
	}
}
void Mesh_reset_v_prop(struct Mesh* mesh)
{
	// for(auto vit=mesh->vertices.begin();vit!=mesh->vertices.end();vit++)
	// {
	//     vit->second->prop=NULL;     
	// }
	for (auto vit = Mesh_v_beginn(mesh); vit != Mesh_v_endn(mesh); vit++)
	{
		((template_v*)(quote(vit)))->prop = NULL;
	}

}
void Mesh_reset_hf_prop(struct Mesh* mesh)
{
	// for(auto hfit=mesh->halffaces.begin();hfit!=mesh->halffaces.end();hfit++)
	// {
	//     hfit->second->prop=NULL;   
	// }
	for (auto hfit = Mesh_hf_beginn(mesh); hfit != Mesh_hf_endn(mesh); hfit++)
	{
		((template_hf*)(quote(hfit)))->prop = NULL;
	}
}
void Mesh_reset_f_prop(struct Mesh* mesh)
{
	// for(auto fit=mesh->faces.begin();fit!=mesh->faces.end();fit++)
	// {
	//     fit->second->prop=NULL; 
	// }
	for (auto fit = Mesh_f_beginn(mesh); fit != Mesh_f_endn(mesh); fit++)
	{
		((quote(fit)))->prop = NULL;
	}
}


iterator_v Mesh_v_beginn(struct Mesh* own)
{
	iterator_v it;
	iterator_v_init(&it);
	it.it = own->vertices->begin(own->vertices);
	return it;
}
iterator_v Mesh_v_endn(struct Mesh* own)
{
	iterator_v it;
	iterator_v_init(&it);
	return it;
}

iterator_hf Mesh_hf_beginn(struct  Mesh* own)
{
	iterator_hf it;
	iterator_hf_init(&it);
	it.it = own->halffaces->begin(own->halffaces);
	return it;
}
iterator_hf Mesh_hf_endn(struct  Mesh* own)
{
	iterator_hf it;
	iterator_hf_init(&it);
	return it;
}

iterator_f Mesh_f_beginn(struct  Mesh* own)
{
	iterator_f it;
	iterator_f_init(&it);
	it.it = own->faces->begin(own->faces);
	return it;
}
iterator_f Mesh_f_endn(struct  Mesh* own)
{
	iterator_f it;
	iterator_f_init(&it);
	return it;
}

iterator_c Mesh_c_beginn(struct Mesh* own)
{
	iterator_c it;
	iterator_c_init(&it);
	it.it = own->cells->begin(own->cells);
	return it;
}
iterator_c Mesh_c_endn(struct Mesh* own)
{
	iterator_c it;
	iterator_c_init(&it);
	return it;
}

iterator_v Mesh_fv_begin(struct Mesh* own, template_f f_)
{

	iterator_v it;
	iterator_v_init(&it);
	it.value = f_.vertices;
	return it;

}

iterator_v Mesh_fv_end(struct Mesh* own, template_f f_)
{
	iterator_v it;
	iterator_v_init(&it);
	it.value = f_.vertices;
	it.i = f_.vertices_size;
	return it;

}
iterator_v Mesh_hfv_begin(struct Mesh* own, template_hf hf)
{
	iterator_v it;
	iterator_v_init(&it);
	it.value = hf.vertices;
	return it;

}
iterator_v Mesh_hfv_end(struct Mesh* own, template_hf hf)
{
	iterator_v it;
	iterator_v_init(&it);
	it.value = hf.vertices;
	it.i = hf.vertices_size;

	return it;
}
iterator_v Mesh_cv_begin(struct Mesh* own, template_c c)
{
	iterator_v it;
	iterator_v_init(&it);
	it.value = c.vertices;
	return it;
}
iterator_v Mesh_cv_end(struct Mesh* own, template_c c)
{
	iterator_v it;
	iterator_v_init(&it);
	it.value = c.vertices;
	it.i = c.vertices_size;
	return it;
}


iterator_f Mesh_vf_begin(struct Mesh* own, template_v v)
{
	iterator_f iff;
	iterator_f_init(&iff);
	if (v.faces == NULL)
	{
		return iff;
	}
	//***********
	//可以通过node->traits记录起点增加速度
	//***************
	iff.node = *(node_reverse(v.faces));

	return iff;

}
iterator_f Mesh_vf_end(struct Mesh* own, template_v v)
{
	iterator_f iff;
	iterator_f_init(&iff);
	return iff;

}
iterator_hf Mesh_chf_begin(struct Mesh* own, template_c c)
{

	iterator_hf iff;
	iterator_hf_init(&iff);
	if (c.halffaces == NULL)
	{
		return iff;
	}
	if (c.halffaces->traits == NULL)
	{
		c.halffaces->traits = (void*)(node_reverse(c.halffaces));
	}
	iff.node = *((Node*)(c.halffaces->traits));

	return iff;
}
iterator_hf Mesh_chf_end(struct Mesh* own, template_c c)
{
	iterator_hf iff;
	iterator_hf_init(&iff);
	return iff;

}
iterator_c Mesh_vc_begin(struct Mesh* own, template_v v)
{
	iterator_c it;
	iterator_c_init(&it);
	if (v.cells == NULL)
	{
		return it;
	}
	it.node = *(v.cells);
	return it;

}
iterator_c Mesh_vc_end(struct Mesh* own, template_v v)
{

	iterator_c it;
	iterator_c_init(&it);
	return it;
}
iterator_edge Mesh_edge_begin(struct Mesh* own, template_v v, template_f f)
{

	iterator_edge ie;
	iterator_edge_init(&ie);
	for (Node* nit = v.faces; nit != NULL; nit = (Node*)(nit->Next))
	{
		template_f* f1 = (template_f*)(nit->value);
		if (f1->id == f.id)
		{
			ie.f = f1;
			break;
		}
	}
	for (int i = 0; i < f.vertices_size; i++)
	{
		if (f.vertices[i]->id == v.id)
		{
			ie.v = f.vertices[i];
			break;
		}
	}
	ie.mark = ie.f;

	return ie;
}
Node* Mesh_vv_begin(struct Mesh* own, template_v v)
{
	if (own->simplex != 1)
	{
		printf("is not simplex\n");
		return NULL;
	}
	Node* node = NULL;
	for (iterator_f fit = Mesh_vf_begin(own, v); fit != Mesh_vf_end(own, v); fit++)
	{
		for (auto vit = Mesh_fv_begin(own, *fit); vit != Mesh_fv_end(own, *fit); vit++)
		{
			if ((*vit).id != v.id)
			{
				if (node_find(node, (void*)quote(vit)) == NULL)
				{
					node = node_overlying(node, (void*)quote(vit));
				}
			}
		}
	}
	return node;
}
Node* Mesh_vv_end(struct Mesh* own, template_v  vv)
{

	return NULL;
}
void Mesh_printself(struct Mesh* own)
{
	printf("****************************\n\n");
	for (auto it = Mesh_v_beginn(own); it != Mesh_v_endn(own); it++)
	{
		printf("id :%d \n", ((template_v*)(quote(it)))->id);
		for (int j = 0; j < ((template_v*)(quote(it)))->point_size; j++)
		{
			printf("%lf  ", ((template_v*)(quote(it)))->point[j]);
		}
		printf("\n");
	}

	printf("faces\n");
	for (auto it = Mesh_f_beginn(own); it != Mesh_f_endn(own); it++)
	{
		printf("id:%d\n", ((template_f*)(quote(it)))->id);
		if (((template_f*)(quote(it)))->prop != NULL)
		{
			printf("prop ");
		}
		for (int j = 0; j < ((template_f*)(quote(it)))->vertices_size; j++)
		{
			printf("id :%d  ", ((template_v*)(((template_f*)(quote(it)))->vertices[j]))->id);

		}
		printf("\n");
	}
	printf("cell\n");
	for (auto it = Mesh_c_beginn(own); it != Mesh_c_endn(own); it++)
	{
		printf("cell id:%d\n", ((template_c*)(quote(it)))->id);
		for (int j = 0; j < ((template_c*)(quote(it)))->vertices_size; j++)
		{
			printf("id %d  ", ((template_v*)(((template_c*)(quote(it)))->vertices[j]))->id);
		}
		printf("\n");
	}
	// for(auto it=own->vertices.begin();it!=own->vertices.end();it++)
	// {
	//     printf("id :%d \n",it->second->id);
	//     for(int j=0;j<it->second->point_size;j++)
	//     {
	//         printf("%lf  ",it->second->point[j]); 
	//     }
	//     printf("\n");
	// }
	// printf("faces\n");
	// for(auto it=own->faces.begin();it!=own->faces.end();it++)
	// {
	//    printf("id:%d\n",it->second->id);
	//    if(it->second->prop!=NULL)
	//    {
	//         printf("prop ");
	//    }
	//    for(int j=0;j<it->second->vertices_size;j++)
	//    {
	//        printf("id :%d  ",((template_v*)(it->second->vertices[j]))->id);

	//    }
	//    printf("\n");
	// }
	// printf("cell\n");
	// for(auto it=own->cells.begin();it!=own->cells.end();it++)
	// {
	//     printf("cell id:%d\n",it->second->id);
	//     for(int j=0;j<it->second->vertices_size;j++)
	//     {
	//         printf("id %d  ",((template_v*)(it->second->vertices[j]))->id);
	//     }
	//     printf("\n");
	// }
	printf("****************************\n\n");

}
Node* Mesh_intersection_two_faces(struct Mesh* own, template_f* f0, template_f* f1)
{
	Node* node = NULL;
	int flag = 1;
	for (int i = 0; i < f0->vertices_size; i++)
	{
		flag = 1;
		for (int j = 0; j < f1->vertices_size; j++)
		{
			if ((f0->vertices[i]) == f1->vertices[j])
			{
				flag = 0;
				break;
			}
		}
		if (flag == 0)
		{
			Node* node = nullptr;
			node_overlying(node, f0->vertices[i]);
		}
	}
	return node;
}

Mesh* mesh_duplicate(struct Mesh* m)
{
	Mesh* re = (Mesh*)malloc(sizeof(Mesh));
	Mesh_init(re);

	re->simplex = m->simplex;
	re->dimension = m->dimension;
	re->manifold_require = m->manifold_require;

	for (auto vit = m->v_begin(m); vit != m->v_end(m); vit++)
	{
		template_v* v = (template_v*)malloc(sizeof(template_v));
		Vertex_init_(v);
		v->id = quote(vit)->id;
		v->point_size = quote(vit)->point_size;
		v->point = (double*)malloc(sizeof(double) * v->point_size);
		memmove(v->point, quote(vit)->point, sizeof(double) * v->point_size);
		re->vertices->insert(re->vertices, v->id, v);
	}


	for (auto fit = m->f_begin(m); fit != m->f_end(m); fit++)
	{
		template_v** vs = (template_v**)malloc(sizeof(template_v*) * quote(fit)->vertices_size);

		for (int i = 0; i < quote(fit)->vertices_size; i++)
		{
			vs[i] = re->get_vertexp(re, quote(fit)->vertices[i]->id);
		}

		re->create_facev(re, vs, quote(fit)->vertices_size);
		free(vs);
	}

	for (auto cit = m->c_begin(m); cit != m->c_end(m); cit++)
	{
		template_hf** hfs = (template_hf**)malloc(sizeof(template_hf*) * node_size(quote(cit)->halffaces));

		int i = 0;
		for (auto chf = m->chf_begin(m, *quote(cit)); chf != m->chf_end(m, *quote(cit)); chf++)
		{
			template_v** vs = (template_v**)malloc(sizeof(template_v*) * quote(chf)->vertices_size);

			for (int j = 0; j < quote(chf)->vertices_size; j++)
			{
				vs[j] = re->get_vertexp(re, quote(chf)->vertices[j]->id);
			}
			template_f* f = re->get_facev(re, vs, quote(chf)->vertices_size);
			template_hf* hf = re->create_halfface(re, f, vs, quote(chf)->vertices_size);

			hfs[i] = hf;
			free(vs);
			i++;
		}

		re->create_cellf(re, hfs, node_size(quote(cit)->halffaces));
		free(hfs);
	}

	return re;
}



void Mesh_free(struct Mesh* own)
{
	if (own == NULL)
	{
		return;
	}
	SAFE_FREE(own->name);
	if (own->external_cell.halffaces != NULL)
	{
		free_node(own->external_cell.halffaces);
		own->external_cell.halffaces = NULL;
	}
	for (auto iter = Mesh_c_beginn(own); iter != Mesh_c_endn(own); iter++)
	{
		free_Cell((template_c*)(quote(iter)));
	}

	for (auto iter = Mesh_f_beginn(own); iter != Mesh_f_endn(own); iter++)
	{
		free_Face((template_f*)(quote(iter)));
	}
	for (auto iter = Mesh_v_beginn(own); iter != Mesh_v_endn(own); iter++)
	{
		free_Vertex((template_v*)(quote(iter)));
	}

	int_rb_tree_free(own->cells);
	int_rb_tree_free(own->faces);
	int_rb_tree_free(own->halffaces);
	int_rb_tree_free(own->vertices);
	own->cells = NULL; own->faces = NULL; own->halffaces = NULL; own->vertices = NULL;
	own->cell_id = 0; own->vertex_id = 0; own->face_id = 0; own->halfface_id = 0;


	// for(auto iter=own->cells.begin();iter!=own->cells.end();iter++)
	// {
	//     free_Cell(iter->second);
	// }
	// for(auto iter=own->faces.begin();iter!=own->faces.end();iter++)
	// {
	//     free_Face(iter->second);
	// } 
	// for(auto iter=own->vertices.begin();iter!=own->vertices.end();iter++)
	// {
	//     free_Vertex(iter->second);
	// }    
	// own->cells.clear();
	// own->faces.clear();
	// own->halffaces.clear();
	// own->vertices.clear(); 
}


void Mesh_init(struct Mesh* own)
{
	own->name = NULL;
	own->faces = (Int_RB_Tree*)malloc(sizeof(Int_RB_Tree));
	own->cells = (Int_RB_Tree*)malloc(sizeof(Int_RB_Tree));
	own->halffaces = (Int_RB_Tree*)malloc(sizeof(Int_RB_Tree));
	own->vertices = (Int_RB_Tree*)malloc(sizeof(Int_RB_Tree));
	int_rb_tree_init((own->cells));
	int_rb_tree_init((own->faces));
	int_rb_tree_init((own->vertices));
	int_rb_tree_init((own->halffaces));
	//own->cells.insert(&(own->cells),9,NULL); 
	// own->vertices=(RB_Tree*)malloc(sizeof(RB_Tree));
	// rb_tree_init_int(own->vertices);
	// own->halffaces=(RB_Tree*)malloc(sizeof(RB_Tree));
	// rb_tree_init_int(own->halffaces);
	// own->faces=(RB_Tree*)malloc(sizeof(RB_Tree));
	// rb_tree_init_int(own->faces);
	// own->cells=(RB_Tree*)malloc(sizeof(RB_Tree));
	// rb_tree_init_int(own->cells);


	Cell_init_(&(own->external_cell));
	own->cell_id = 0; own->vertex_id = 0; own->face_id = 0; own->halfface_id = 0;
	own->get_vertexp = Mesh_get_vertexp;


	own->get_facep = Mesh_get_facep;
	own->get_halffacep = Mesh_get_halffacep;
	own->get_cellp = Mesh_get_cellp;
	own->get_vertex = Mesh_get_vertex;
	own->get_cell = Mesh_get_cell;
	own->get_face = Mesh_get_face;
	own->get_halfface = Mesh_get_halfface;
	own->get_facev = Mesh_get_facev;
	own->get_cellv = Mesh_get_cellv;
	own->get_cellf = Mesh_get_cellf;
	own->num_v = Mesh_num_v;
	own->num_c = Mesh_num_c;
	own->num_f = Mesh_num_f;
	own->num_hf = Mesh_num_hf;
	own->create_vertex = Mesh_create_vertex;
	own->create_vertexv = Mesh_create_vertexv;
	own->create_cell = Mesh_create_cell;
	own->create_face = Mesh_create_face;
	own->create_cellv = Mesh_create_cellv;
	own->create_cellf = Mesh_create_cellf;
	own->create_facev = Mesh_create_facev;
	own->create_halfface = Mesh_create_halfface;
	own->delete_cell = Mesh_delete_cell;
	own->delete_vertex = Mesh_delete_vertex;
	own->delete_face = Mesh_delete_face;
	own->delete_halfface = Mesh_delete_halfface;
	own->vertex_is_boundary = Mesh_vertex_is_boundary;
	own->face_is_boundary = Mesh_nface_is_boundary;
	own->cell_is_boundary = Mesh_cell_is_boundary;
	own->face_is_in_cell = Mesh_face_is_in_cell;
	own->vertex_is_in_cell = Mesh_vertex_is_in_cell;
	own->vertex_is_in_face = Mesh_vertex_is_in_face;

	own->node_of_boundary_face = Mesh_node_of_boundary_face;
	own->external_cell_init_ = Mesh_external_cell_init_;
	own->opposite_halfface = Mesh_opposite_halfface;
	own->s_opposite_halfface = Mesh_s_opposite_halfface;


	own->v_begin = Mesh_v_beginn;
	own->v_end = Mesh_v_endn;
	own->f_begin = Mesh_f_beginn;
	own->f_end = Mesh_f_endn;
	own->hf_begin = Mesh_hf_beginn;
	own->hf_end = Mesh_hf_endn;
	own->c_begin = Mesh_c_beginn;
	own->c_end = Mesh_c_endn;

	own->cv_begin = Mesh_cv_begin;
	own->cv_end = Mesh_cv_end;
	own->fv_begin = Mesh_fv_begin;
	own->fv_end = Mesh_fv_end;
	own->hfv_begin = Mesh_hfv_begin;
	own->hfv_end = Mesh_hfv_end;
	own->vc_begin = Mesh_vc_begin;
	own->vc_end = Mesh_vc_end;
	own->vf_begin = Mesh_vf_begin;
	own->vf_end = Mesh_vf_end;
	own->chf_begin = Mesh_chf_begin;
	own->chf_end = Mesh_chf_end;
	own->vv_begin = Mesh_vv_begin;
	own->vv_end = Mesh_vv_end;
	own->edge_begin = Mesh_edge_begin;
	own->intersection_two_faces = Mesh_intersection_two_faces;
	own->non_manifold_vertices = Mesh_non_manifold_vertices;
	own->printself = Mesh_printself;

	own->reset_f_prop = Mesh_reset_f_prop;
	own->reset_hf_prop = Mesh_reset_hf_prop;
	own->reset_c_prop = Mesh_reset_c_prop;
	own->reset_v_prop = Mesh_reset_v_prop;




	own->simplex = 1;
	own->dimension = -1;
	own->manifold_require = 1;

	own->prop = NULL;
	meshT_init(&(own->traits));
}

